//Non-Manifold Vertice display function
import java.util.concurrent.ConcurrentLinkedQueue;

pt rotateTheta(pt a, pt b, vec v, float theta){ //Thanks to Glenn Murray, http://inside.mines.edu/~gmurray/ArbitraryAxisRotation/
  pt rot = new pt();
  rot.x = (b.x*(sq(v.y)+sq(v.z)) - v.x*(b.y*v.y + b.z*v.z - v.x*a.x - v.y*a.y - v.z*a.z))*(1-cos(theta)) + a.x*cos(theta) + (-b.z*v.y + b.y*v.z - v.z*a.y + v.y*a.z)*sin(theta);
  rot.y = (b.y*(sq(v.x)+sq(v.z)) - v.y*(b.x*v.x + b.z*v.z - v.x*a.x - v.y*a.y - v.z*a.z))*(1-cos(theta)) + a.y*cos(theta) + (b.z*v.x - b.x*v.z + v.z*a.x - v.x*a.z)*sin(theta);
  rot.z = (b.z*(sq(v.x)+sq(v.y)) - v.z*(b.x*v.x + b.y*v.y - v.x*a.x - v.y*a.y - v.z*a.z))*(1-cos(theta)) + a.z*cos(theta) + (-b.y*v.x + b.x*v.y - v.y*a.x + v.x*a.y)*sin(theta);
  return rot;
}

pt rotate90(pt a, pt b, vec v){
  return rotateTheta(a,b,v,PI/2);
}

pt rotate90(int a, int b, vec v){
  return rotate90(M.G[a],M.G[b],v);
}

pt rotate90(int a, int b){
  return rotate90(M.G[a],M.G[b],V(M.G[a],M.G[b]));
}

vec vecRotate90(int a, int b, vec v){
  return V(M.G[b],rotate90(a,b,v));
}

pt closestPoint(pt a, pt b, pt c){
  float distance = d(a,c);
  float distance2 = d(b,c);
  if(distance < distance2){
    return a;
  } else {
    return b;
  }
}

pt closestToOrigin(pt a, pt b){
  return closestPoint(a,b,new pt(-10000,-10000,-10000));
}

boolean clockwise(pt a, pt b, pt c) { //determine if three points are oriented in a clockwise direction
  return n(N(V(a,b), V(b,c))) > 0; 
}

boolean clockwise2(pt a, pt b, pt c){
  vec v = N(a,b,c);
  if(d(v,V(b,new pt(0,0,b.z+1))) > 0){
    drawSphere(b.x+v.x/1000,b.y+v.y/1000,b.z+v.z/1000,10);
  }
  return d(v,V(b,new pt(0,0,b.z+1))) < 0;
}

boolean clockwise2(pt a, pt b, pt c, color d){
  vec v = N(a,b,c);
  if(d(v,V(b,new pt(0,0,b.z+1))) > 0){
    drawSphere(b.x+v.x/1000,b.y+v.y/1000,b.z+v.z/1000,10,d);
  }
  return d(v,V(b,new pt(0,0,b.z+1))) < 0;
}

boolean lineIntersection(pt a, pt aLeft, pt aRight, pt b, pt c, pt d){
  vec normalA = N(V(a,aLeft),V(a,aRight)).normalize();
  pt an = new pt(a.x+normalA.x,a.y+normalA.y,a.z+normalA.z);
  return (cw(an,a,b,c)!=cw(an,a,b,d) && cw(an,c,d,a)!=cw(an,c,d,b));
}

boolean pointInTriangle(pt p, pt a, pt b, pt c){
  boolean x = clockwise(a,p,b);
  boolean y = clockwise(b,p,c);
  boolean z = clockwise(c,p,a);
  return x==y && x==z;
}


void drawNonManifoldVerts(){
  ArrayList<pt> vertList = findNonManifoldVerts();
  
  fill(color(0,255,0));
  for(pt vert : vertList){
    drawSphere(vert.x,vert.y,vert.z,7);
  }
  noFill();
  
}

ArrayList<pt> findNonManifoldVerts(){
  ArrayList<Integer> triCountList = new ArrayList<Integer>();
  ArrayList<pt> vertList = new ArrayList<pt>();
  int count = 0;
  for(pt vert : M.G){ //count the number of triangles with each vertex
    count++;
    int pcount = 0;
    pt a = vert;
    for(int i = 0; i<M.nt*3; i++){
      pt p = M.G[M.V[i]];
        if(pointsEqual(vert,p)){
        pcount++;
//        printpt(a);
//        printpt(p);
      }
    }
//    println(pcount);
    triCountList.add(pcount);
//    println("list size " + triCountList.size());
//    println("g size " + M.nv);
//    drawSphere(a.x,a.y,a.z,5);
    if(count>=M.nv) break;
  }
  for(int i = 0; i < triCountList.size(); i++){
    if(triCountList.get(i) != countSwings(findClosestCorner(M.G[i])))
    {
      vertList.add(M.G[i]);
    }
  }
//  println("------------------------------");
  return vertList;
}

ArrayList<Integer> findNonManifoldVerts(ArrayList<Integer> verts){
  ArrayList<Integer> triCountList = new ArrayList<Integer>();
  ArrayList<Integer> vertList = new ArrayList<Integer>();
//  ArrayList<pt> vertPts = new ArrayList<pt>();
//  for(Integer i : verts){
//    vertPts.add(M.G[i.intValue]);
//  }
  int count = 0;
  for(Integer vert : verts){ //count the number of triangles with each vertex
    count++;
    int pcount = 0;
    pt a = M.G[vert.intValue()];
    for(int i = 0; i<M.nt*3; i++){
      pt p = M.G[M.V[i]];
        if(pointsEqual(M.G[vert.intValue()],p)){
        pcount++;
//        printpt(a);
//        printpt(p);
      }
    }
//    println(pcount);
    triCountList.add(pcount);
//    println("list size " + triCountList.size());
//    println("g size " + M.nv);
//    drawSphere(a.x,a.y,a.z,5);
    if(count>=M.nv) break;
  }
  for(int i = 0; i < triCountList.size(); i++){
    if(triCountList.get(i) != countSwings(findClosestCorner(M.G[verts.get(i).intValue()])))
    {
//      println("nons " + );
      drawSphere(M.G[verts.get(i).intValue()],10);
      countSwingsAndSplit(findClosestCorner(M.G[verts.get(i).intValue()]));
      vertList.add(i);
    }
  }
//  println("------------------------------");
  return vertList;
}

void drawSphere(float x, float y, float z, int sze, color c)
{
  fill(c);
  pushMatrix();
  translate(x,y,z);
  sphere(sze);
  popMatrix();
  noFill();
}

void drawSphere(float x, float y, float z, int sze){
  drawSphere(x,y,z,sze,color(0,255,0));
}

void drawSphere(pt p, int sze){
  drawSphere(p.x,p.y,p.z,sze);
}

void drawSphere(pt p, int sze, color c){
  drawSphere(p.x,p.y,p.z,sze,c);
}

void drawSphere(pt p){
  drawSphere(p,1);
}

boolean pointsEqual(pt a, pt b){
  return a.x == b.x && a.y == b.y && a.z == b.z;
}

void printpt(pt a){
  StringBuffer strib = new StringBuffer();
  strib.append("Pt ");
  strib.append(a.x + " ");
  strib.append(a.y + " ");
  strib.append(a.z + " ");
  println(strib);
}

void printvec(vec a){
  StringBuffer strib = new StringBuffer();
  strib.append("Vec ");
  strib.append(a.x + " ");
  strib.append(a.y + " ");
  strib.append(a.z + " ");
  println(strib);
}

ArrayList<Integer> findNeighboringVerts(int v){
  ArrayList<Integer> neighborVerts = new ArrayList<Integer>();
  int tri = -1;
  int vertCount = 0;
  for(int i = 0; i<M.nt*3; i++){
    if(M.V[i] == v){
      tri = i/3;
      vertCount++;
    }
  }
//  for(int i = 0; i<M.nv; i++){
//    if(M.G[i].x == M.G[v].x && M.G[i].y == M.G[v].y && M.G[i].z == M.G[v].z && i!=v){
//      vertCount++;
//    }
//  }
  int corn = M.c(tri);
//  println(v);
//  println(tri);
//  println(corn);
  if(M.v(corn) == v){
    corn = M.p(corn);
  } else if(M.v(M.p(corn)) == v) {
    corn = M.n(corn);
  }
  if(vertCount != 6) vertCount = 6;
  for(int i = 0; i<vertCount; i++){
    neighborVerts.add(M.v(corn));
    corn=M.n(M.o(corn));
  }
  int siz = neighborVerts.size();
  for(int n = 0; n<siz; n++){
    for(int i = 0; i<M.nv; i++){
      if(pointEquals(M.G[neighborVerts.get(n).intValue()],M.G[i]) && neighborVerts.get(n).intValue()!=i ){
        neighborVerts.add(i);
      }
    }
  }

return neighborVerts;

}

ArrayList<Integer> findNeighboringVertsList(int v, ArrayList<Integer> verts){
  ArrayList<Integer> neighborsInList = new ArrayList<Integer>();
  ArrayList<Integer> neighbors = findNeighboringVerts(v);
  for(Integer neighbor : neighbors){
    if(verts.contains(neighbor) && !pointEquals(M.G[v],M.G[neighbor.intValue()])){
      neighborsInList.add(neighbor);
    }
  }
  return neighborsInList;
}

int[] findNeighboringVerts(int v, ArrayList<Integer> verts){
  int secondVert = -1;
  SpanningTree forFuncs = new SpanningTree();
  int[] neighborsInList = new int[2];
  ArrayList<Integer> neighbors = findNeighboringVerts(v);
  int count = 0;
  for(Integer neighbor : neighbors){
//    println("n "+ neighbor);
    if(verts.contains(neighbor) && !pointEquals(M.G[v],M.G[neighbor.intValue()])){
      if(count == 0 || (count > 0 && !pointEquals(M.G[neighbor.intValue()],M.G[neighborsInList[0]]))){
//        if(!usedVerts.contains(M.v(neighbor.intValue()))){
//        if(!forFuncs.contains2(new Edge(v,neighbor),usedVerts)){
          neighborsInList[count] = neighbor.intValue();
          count++;
//        }
      }
    }
    if(count>1) break;
  }
  if(count == 1){
//    for(int i = 0; i<M.nv; i++){
//      if(pointEquals(M.G[i], M.G[neighborsInList[0]]) && i!=neighborsInList[0] && !pointEquals(M.G[i],M.G[neighborsInList[0]])){
//        secondVert = i;
//        break;
//      }
//    }
    neighborsInList[count]=secondVert;
  }
//  println("size " + neighbors.size());
  if(neighborsInList[1]!=-1 && pointEquals(M.G[neighborsInList[1]],closestToOrigin(M.G[neighborsInList[0]],M.G[neighborsInList[1]]))){
    int temp = neighborsInList[0];
    neighborsInList[0]=neighborsInList[1];
    neighborsInList[1] = temp;
  }
  return neighborsInList;
    
}

int[] findNeighboringVertsComb(int a, int b, ArrayList<Integer> verts){
  int[] first =(findNeighboringVerts(a,verts));
  int[] secnd = (findNeighboringVerts(b,verts));
  if(first[0] == secnd[0]){
    int[] combined = {first[0],secnd[1]};
    if(combined[1]!=-1 && pointEquals(M.G[combined[1]],closestToOrigin(M.G[combined[0]],M.G[combined[1]])) && combined[1]!=-1){
      int temp = combined[0];
      combined[0]=combined[1];
      combined[1] = temp;
    }
    return combined;
  } else {
    int[] combined = {first[0],secnd[0]};
    if(combined[1]!=-1 && pointEquals(M.G[combined[1]],closestToOrigin(M.G[combined[0]],M.G[combined[1]]))){
      int temp = combined[0];
      combined[0]=combined[1];
      combined[1] = temp;
    }
    
    return combined;
  }
}

ArrayList<Integer> findNeighboringVerts2(int v){
  ArrayList<Integer> neighborVerts = new ArrayList<Integer>();
  int tri = -1;
  int vertCount = 0;
  for(int i = 0; i<M.nt*3; i++){
    if(M.V[i] == v){
      tri = i/3;
      vertCount++;
    }
  }
//  for(int i = 0; i<M.nv; i++){
//    if(M.G[i].x == M.G[v].x && M.G[i].y == M.G[v].y && M.G[i].z == M.G[v].z && i!=v){
//      vertCount++;
//    }
//  }
  int corn = M.c(tri);
//  println(v);
//  println(tri);
//  println(corn);
  if(M.v(corn) == v){
    corn = M.p(corn);
  } else if(M.v(M.p(corn)) == v) {
    corn = M.n(corn);
  }
  
  for(int i = 0; i<vertCount; i++){
    if(!neighborVerts.contains(M.v(corn))){
      neighborVerts.add(M.v(corn));
    }
    corn=M.n(M.o(corn));
  }

return neighborVerts;

}

int[] findNeighboringVerts2(int v, ArrayList<Integer> verts){
  int secondVert = -1;
  
  int[] neighborsInList = new int[4];
  ArrayList<Integer> neighbors = findNeighboringVerts2(v);
  int count = 0;
  for(Integer neighbor : neighbors){
//    println("n "+ neighbor);
    if(verts.contains(neighbor) && !pointEquals(M.G[v],M.G[neighbor])){
      neighborsInList[count] = neighbor.intValue();
      count++;
      if (count == 4) break;
    }
    
  }
//  if(count == 1){
//    for(int i = 0; i<M.nv; i++){
//      if(M.G[i].x == M.G[neighborsInList[0]].x && M.G[i].y == M.G[neighborsInList[0]].y && M.G[i].z == M.G[neighborsInList[0]].z && i!=neighborsInList[0]){
//        secondVert = i;
//        break;
//      }
//    }
//    neighborsInList[count]=secondVert;
//  }


  return neighborsInList;
    
}

ArrayList<Integer> getTriangles(int vert){
  ArrayList<Integer> tris = new ArrayList<Integer>();
  for(int i = 0; i<M.nt*3; i++){
    if(M.V[i] == vert){
      tris.add(i/3);
//      println("tris " + i/3);
    }
  }
  return tris;
}

int[] sharedTriangles(int va, int vb){
  ArrayList<Integer> ta = getTriangles(va);
  ArrayList<Integer> tb = getTriangles(vb);
  int count = 0;
  int[] shared = new int[2];
  for(Integer i : ta){
    if(tb.contains(i.intValue())){
      shared[count] = i.intValue();
      count++;
    }
    if(count > 1) break;
  }
  if(count==1){
    shared[1]=-1;
  }
  if(count==0){
    shared = null;
  }
  return shared;
}

int[] sharedTriangles(int va, int vb, int vc){
  int[] ab = sharedTriangles(va,vb);
  int[] ac = sharedTriangles(va,vc);
  println(va + "," + vb + "," + vc);
  println(ab[0] + "," + ab[1]);
  println(ac[0] + "," + ac[1]);
  int[] combined = {ab[0],ac[0]};
  return combined;
}


int findClosestCorner(pt vert){
  pt corn = new pt();
  int cornIndex = -1;
  float minDistance = Float.MAX_VALUE;
  for(int i = 0; i<M.nc; i++){
    pt p = M.g(i);
    if(pointsEqual(p,vert)){
      corn = M.cg(i);
      cornIndex = i;
      break;
    }
  }
//  println(cornIndex);
//  printpt(M.cg(cornIndex));
  return cornIndex;
}

int findClosestCorner2(pt vert){
  pt corn = new pt();
  int answer = 0;
  int cornIndex = -1;
  float minDistance = Float.MAX_VALUE;
  for(int i = 0; i<M.nc; i++){
    corn = M.cg(i);
    float distance = distanceOf(corn,vert);
    if(distance < minDistance){
      answer = i;
      minDistance = distance;
    }
  }
  return answer;
}

int findCorner(pt vert){
  for(int i = 0; i<M.nc; i+=3){
    if(pointInTriangle(vert,M.G[M.V[i]],M.G[M.V[i+1]],M.G[M.V[i+2]])){
      return(M.c(i));
    }
  }
  return -1;
}

int countSwings(int cornIndex){
  int triCount = 0;
  int currCorn = cornIndex;
  int borderCount = 0;
  int prevTri = -1;
  int currTri = M.t(cornIndex);
  ArrayList<Integer> visited = new ArrayList<Integer>();
  while(prevTri != currTri && !visited.contains(currTri)){
//    println(prevTri + " " + currTri);
    visited.add(currTri);
    prevTri = currTri;
    currCorn = M.s(currCorn);
    currTri = M.t(currCorn);
    triCount++;
  }
  prevTri = M.t(cornIndex);
  currCorn = M.u(cornIndex);
  currTri = M.t(currCorn);
  while(prevTri != currTri && !visited.contains(currTri)){
//    println(prevTri + " " + currTri);
    visited.add(currTri);
    prevTri = currTri;
    currCorn = M.u(currCorn);
    currTri = M.t(currCorn);
    triCount++;
  }
  return triCount;
}

int countSwingsAndSplit(int cornIndex){
  int triCount = 0;
  int currCorn = cornIndex;
  int borderCount = 0;
  int prevTri = -1;
  int currTri = M.t(cornIndex);
  ArrayList<Integer> visited = new ArrayList<Integer>();
  while(prevTri != currTri && !visited.contains(currTri)){
//    println(prevTri + " " + currTri);
    visited.add(currTri);
    prevTri = currTri;
    currCorn = M.s(currCorn);
    currTri = M.t(currCorn);
    triCount++;
  }
  prevTri = M.t(cornIndex);
  currCorn = M.u(cornIndex);
  currTri = M.t(currCorn);
  while(prevTri != currTri && !visited.contains(currTri)){
//    println(prevTri + " " + currTri);
    visited.add(currTri);
    prevTri = currTri;
    currCorn = M.u(currCorn);
    currTri = M.t(currCorn);
    triCount++;
  }
  
  int vert = M.v(cornIndex);
  pt p = new pt(M.G[vert].x,M.G[vert].y,M.G[vert].z);
  M.G[M.nv] = p;
  for(int j = 0; j<M.nt*3; j++){
    if(visited.contains(j/3) && M.V[j] == vert){
//      println("j/3 " + j/3);
      M.V[j] = M.nv;
    }
  }
  M.nv++;
  return triCount;
}

PathTree createPathTree(int startingIndex){ //create a tree with a starting triangle at the root and a path to all other triangles
  PathTree path = new PathTree();
  ArrayList<Integer> unvisitedTri = new ArrayList<Integer>();
  ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<Integer>();
  int firstCorn = startingIndex;
  int currCorn = firstCorn;
  int leftCorn = M.l(firstCorn);
  int rightCorn = M.r(firstCorn);
  for(int i = 0; i < M.nt; i++){
    unvisitedTri.add(i);
  }
//  println("----------------------");
  queue.add(firstCorn);
  unvisitedTri.remove(unvisitedTri.indexOf(M.t(firstCorn)));
  
  while(!unvisitedTri.isEmpty()){
    currCorn = queue.poll();
    leftCorn = M.l(currCorn);
    rightCorn = M.r(currCorn);
    if(unvisitedTri.contains(M.t(leftCorn))){
      queue.add(leftCorn);
    }
    if(unvisitedTri.contains(M.t(rightCorn))){
      queue.add(rightCorn);
    }
    if(unvisitedTri.contains(M.t(currCorn))){
      unvisitedTri.remove(unvisitedTri.indexOf(M.t(currCorn)));
    }
    if(M.t(currCorn) != queue.peek()){
      path.addTriangle(M.t(currCorn));
    }
  }
  return path;
}

PathTree createPathTree(int startingIndex, int endingIndex){ //create a tree with a starting triangle at the root and a path to all other triangles
  PathTree path = new PathTree();
  ArrayList<Integer> unvisitedTri = new ArrayList<Integer>();
  ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<Integer>();
  int firstCorn = startingIndex;
  int currCorn = firstCorn;
  int leftCorn = M.l(firstCorn);
  int rightCorn = M.r(firstCorn);
  for(int i = 0; i < M.nt; i++){
    unvisitedTri.add(i);
  }
//  println("----------------------");
  queue.add(firstCorn);
  unvisitedTri.remove(unvisitedTri.indexOf(M.t(firstCorn)));
  
  while(!unvisitedTri.isEmpty() && M.t(currCorn) != endingIndex){
    currCorn = queue.poll();
    leftCorn = M.l(currCorn);
    rightCorn = M.r(currCorn);
    if(unvisitedTri.contains(M.t(leftCorn))){
      queue.add(leftCorn);
    }
    if(unvisitedTri.contains(M.t(rightCorn))){
      queue.add(rightCorn);
    }
    if(unvisitedTri.contains(M.t(currCorn))){
      unvisitedTri.remove(unvisitedTri.indexOf(M.t(currCorn)));
    }
    if(M.t(currCorn) != queue.peek()){
      path.addTriangle(M.t(currCorn));
    }
  }
  path.addTriangle(M.t(currCorn));
  return path;
}

float distanceOf(pt a, pt b){
  return sqrt(sq(a.x-b.x)+sq(a.y-b.y)+sq(a.z-b.z));
}

ArrayList<Integer> numOfTriInPath;
void makeMinSpanTree(){//rewrite to check if point is inside triangles, distance may grab wrong corners
      SpanningTree stree = new SpanningTree();
      ArrayList<Integer> CPtoCorn = new ArrayList<Integer>();
      for(pt p : CP){
        CPtoCorn.add(findClosestCorner2(p));
//        CPtoCorn.add(findCorner(p));
      }
      for(Integer p : CPtoCorn){
        for(Integer p2 : CPtoCorn){
          if(p.intValue()!=p2.intValue()){
            
            stree.addEdge(p,p2,M.computePath(p.intValue(),p2.intValue()));
          }
        }
      }
      minEdges = stree.minimumSpanningTree();
      triInMinTree = new ArrayList<Integer>();
      numOfTriInPath = new ArrayList<Integer>();
      for(Edge e : minEdges){
        numOfTriInPath.add(M.computePath(e.start,e.end));
      }
//      println(triInMinTree.size());
}

ArrayList<Integer> gatherVertices(){
  if(triInMinTree.isEmpty()) return null;
  ArrayList<Integer> verts = new ArrayList<Integer>();
  Collections.sort(triInMinTree);
//  int next = 0;
//  for(int i = 0; i<triInMinTree.size();i++){
//    if(!verts.contains(M.v(M.c(triInMinTree.get(i))))){
//      verts.add(M.v(M.c(triInMinTree.get(i))));
//      drawSphere(M.G[verts.get(verts.size()-1)],10);
//    }
//    if(i-2>=0  && M.v(M.c(triInMinTree.get(i))) == M.v(M.n(M.c(triInMinTree.get(i-2))))){
//      verts.add(M.v(M.n(M.c(triInMinTree.get(i)))));
//      drawSphere(M.G[verts.get(verts.size()-1)],10);
//
//    } else if(i-2>=0  && M.v(M.c(triInMinTree.get(i))) == M.v(M.p(M.c(triInMinTree.get(i-2))))){
//      verts.add(M.v(M.p(M.c(triInMinTree.get(i)))));
//      drawSphere(M.G[verts.get(verts.size()-1)],10);
//    }
//  }

//  int base = 0;
//  int sum = 0;
//  println("---------------");
//  for(Edge e : minEdges){
//    if(e.start > e.end){
//      int s = e.start;
//      e.start = e.end;
//      e.end = s;
//    }
//  Collections.sort(triInMinTree);
//    println(e.toString());
//  }
//  int count = 0;
//  Collections.sort(minEdges,new EdgeCompare2());
//  for(Integer i : numOfTriInPath){
//    sum+=i;
//  } 
//  println(sum);
//  println(triInMinTree.size());
//  for(int i = 0; i<numOfTriInPath.size(); i++){
//    for(int j = base; j<base + numOfTriInPath.get(i); j++){
//      for(int k = 0; k<3; k++){
//        count++;
//        int vert = M.V[k+(triInMinTree.get(j)*3)];
//        println("Edge: " + i + " Triangle: " + triInMinTree.get(j) + " Vert: " + k);
//        if(clockwise2(M.cg(minEdges.get(i).start),M.G[vert],M.cg(minEdges.get(i).end),color(count*5))){
//          verts.add(vert);
////          drawSphere(M.G[verts.get(verts.size()-1)],10);
//        }
//      }
//    }
//    base += numOfTriInPath.get(i);
//  }

//  for(Edge e : minEdges){
//    int tris = M.t(e.start);
//    int trie = M.t(e.end);
//    for(int i = 0; i<3; i++){
//      int vert = M.V[tris*3 + i];
//      if(clockwise2(M.cg(e.start),M.G[vert],M.cg(e.end))){
//        verts.add(vert);
//        drawSphere(M.G[verts.get(verts.size()-1)],10);
//      }
//      
//    }
//  }

//base on triangles in same path share edge, dont use edge
//  Collections.sort(triInMinTree);
//  SpanningTree forFuncs = new SpanningTree();
//  ArrayList<Edge> innerEdges = new ArrayList<Edge>();
//  ArrayList<Edge> outerEdges = new ArrayList<Edge>();
//  for(int i = 0; i<triInMinTree.size(); i++){
//    for(int j = 0; j<3; j++){
//      int vert = j + M.c(triInMinTree.get(i));
//      Edge e = new Edge(M.V[(j+1)%3 + M.c(triInMinTree.get(i))],M.V[(j+2)%3+M.c(triInMinTree.get(i))]);
//      if(triInMinTree.contains(M.t(M.o(M.c(triInMinTree.get(i))+j))) && M.t(M.o(M.c(triInMinTree.get(i))+j)) != triInMinTree.get(i)){
//        innerEdges.add(e);
//      } else {
//        if(!forFuncs.contains2(e,outerEdges)){
//          outerEdges.add(e);
//        }
//      }
//    }
//  }
////  for(Edge e: outerEdges){
////    println(e.toString());
////  }
////    println("-----------");
////    for(int i = 0; i<triInMinTree.size(); i++) println(triInMinTree.get(i));
////  println(M.V[triInMinTree.get(0)*3]);
//  verts.add(M.V[triInMinTree.get(0)*3]);
////  println(outerEdges.get(0).end);
//  drawSphere(M.G[verts.get(verts.size()-1)],10);
//  int vert1 = verts.get(verts.size()-1);
//  int vert2 = vert1;
//  
//  boolean lastVert = false;
//  while(!lastVert){
//    vert1 = vert2;
//    vert2 = forFuncs.getStart(vert1,outerEdges);
//    
//    if(vert2 != -1 && !verts.contains(vert2) ){
//      if(vert2>vert1){
////        println(vert2);
//        verts.add(vert2);
//        drawSphere(M.G[verts.get(verts.size()-1)],10);
//      }
//
//    } else {
//      lastVert=true;
//    }
//    
//  }
//  verts = new ArrayList<Integer>();
  ArrayList<Integer> sharedBorders = new ArrayList<Integer>();
  ArrayList<Integer> treecopy = (ArrayList<Integer>) triInMinTree.clone();
//  Collections.sort(triInMinTree);
  boolean reiterate = true;
  while(reiterate){
//    println("======???=======");
    reiterate = false;
    for(int i = 0; i<treecopy.size(); i++){
      for(int j = 0; j<treecopy.size(); j++){
        if(i!=j){
          for(int k = treecopy.get(i).intValue()*3; k<treecopy.get(i).intValue()*3+3; k++){
            for(int l = treecopy.get(j).intValue()*3; l<treecopy.get(j).intValue()*3+3; l++){
              if(M.t(M.o(k))==M.t(M.o(l))){
                Integer t = M.t(M.o(l));
//                println(t);
                if(!sharedBorders.contains(t.intValue())){ sharedBorders.add(t); reiterate=true;}
  //              println(sharedBorders.size());
  //              triInMinTree.add(t);
              }  
            }
          }
        }
      }
    }
//    println("=====!!!======");
    for(Integer i : sharedBorders){
      if(!treecopy.contains(i)){
        treecopy.add(i);
      }
//      println(i);
    }
  }
  for(Integer i : treecopy){
    if(triInMinTree.contains(i)){
    verts = M.splitEdges(i.intValue(),treecopy,verts);
    } else {
      M.splitEdges(i.intValue(),treecopy,verts);
    }
  }
//  for(int i = 0; i<sharedBorders.size(); i++){
//    triInMinTree.remove(sharedBorders.get(i));
//  }
//  println("=============");
//  for(Integer i : sharedBorders){
//    println(i);
//  }
//  println("=============");
//  for(Integer i : triInMinTree){
//    println(i);
//  }
  M.updateON();


  return verts;
}


//ArrayList<Edge> usedVerts = new ArrayList<Edge>();
ArrayList<vec> moveVerts = new ArrayList<vec>();
void splitVerts(boolean run){
  ArrayList<Integer> verts = vertsToSplit;
  ArrayList<Integer> added = new ArrayList<Integer>();
  for(int i = 0; i< verts.size(); i++){
    added.add(verts.get(i).intValue());
  }
  if(run){
//    for(Integer vert : verts){
//      int[] neighborSplits = new int[2];
//      ArrayList<Integer> neighbors = findNeighboringVerts(vert);
//      int count = 0;
//      for(Integer neighbor : neighbors){
//        if(vertsToSplit.contains(neighbor)){
//          neighborSplits[count] = neighbor.intValue();
//          count++;
//        }
//        if(count>1) break;
//      }
      
//      int vertCount = 0;
//      int tri = -1;
//      for(int i = 0; i<M.nt*3; i++){
//        if(M.V[i] == vert){
//          vertCount++;
//          tri = i/3;
//        }
//      }
//      int corn = M.c(tri);
//      if(M.v(corn) == vert){
//        corn = M.p(corn);
//      } else if(M.v(M.p(corn)) == vert) {
//        corn = M.n(corn);
//      }
//      boolean markTri = false;
//      ArrayList<Integer> marked = new ArrayList<Integer>();
//      for(int i = 0; i< vertCount; i++){
//        if(markTri){
//          marked.add(M.t(corn));
//        }
//        corn = M.n(M.o(corn));
//        if(lineIntersection(M.G[neighborSplits[0]], M.G[M.v(M.n(M.c(tri)))], M.G[M.v(M.p(M.c(tri)))], M.G[neighborSplits[1]], M.cg(corn), M.cg(M.o(corn)))){
//          markTri = !markTri;
//        }
//        
//      }
//      
//      pt p = new pt(M.G[vert].x,M.G[vert].y,M.G[vert].z);
//      M.G[M.nv] = p;
//      
//      for(int j = 0; j<M.nt*3; j++){
//        if(marked.contains(j/3) && M.V[j] == vert){
//          M.V[j] = M.nv;
//        }
//      }
      
//      for(int i = 0; i<M.nc; i++){
//        if(vert.intValue() == M.V[i] && !triInMinTree.contains(i/3)){
//          M.V[i] = M.nv;
//        }
//      }
      
//      M.nv++;
//    }

//    usedVerts = new ArrayList<Edge>();
    SpanningTree vertTree = new SpanningTree();
    for(int i = 0; i < verts.size(); i++){
      ArrayList<Integer> neighborVerts = findNeighboringVertsList(verts.get(i),verts);
      for(int j = 0; j < neighborVerts.size(); j++){
        Edge e = new Edge(verts.get(i),neighborVerts.get(j),1);
        vertTree.addEdge(e);
      }
    }
//    ArrayList<Edge> vertMinTree = vertTree.minimumSpanningTree();
//    ArrayList<Edge> vertMinTree = new ArrayList<Edge>();
    for(int i = 0; i < verts.size(); i++){
//      usedVerts.add(verts.get(i-1));
      int vert = verts.get(i);
//      println(vert);
      int compareVert;
//      if(i==0){
//        compareVert = verts.get(i+1);
//      } else {
//        compareVert = verts.get(i-1);
//      }
      int [] neighbors = findNeighboringVerts(vert,added);
      ArrayList<Integer> closeTriangles = getTriangles(vert);
//      println(neighbors[0] + " " + neighbors[1]);
      if(/*vertTree.contains2(new Edge(vert, neighbors[0]),vertMinTree) &&*/ neighbors[1]!=-1){
          
//        usedVerts.add(new Edge(verts.get(i),neighbors[0],1));
        int[] sharedTs = sharedTriangles(vert,neighbors[0]);
        if(sharedTs == null){
  //        pt g = M.G[neighbors[0]];
  //        ArrayList<Integer> allNeighbors = findNeighboringVerts(vert);
  //        float distance = 0;
  //        int farthestVert = -1;
  //        for(Integer v : allNeighbors){
  //          float testDist = d(M.G[v],g);
  //          if(testDist > distance){
  //            distance = testDist;
  //            farthestVert = v;
  //          }
  //        }
  //        neighbors[1] = farthestVert;
  //        sharedTs = sharedTriangles(vert,farthestVert);
        } else if(sharedTs[1]==-1){
          for(int j = 0; j<M.nv; j++){
            if(M.G[j].x == M.G[neighbors[0]].x && M.G[j].y == M.G[neighbors[0]].y && M.G[j].z == M.G[neighbors[0]].z && j!=neighbors[0]){
              try{
              sharedTs=sharedTriangles(vert,neighbors[0],j);
              } catch (Exception e){
                println(e.toString());
              }
              break;
            }
          }
        }
        
        int[] sharedTs2 = sharedTriangles(vert,neighbors[1]);
        println(neighbors[0] + "-=-" + neighbors[1]);
        if(sharedTs2 == null){
  //        pt g2 = M.G[neighbors[1]];
  //        ArrayList<Integer> allNeighbors2 = findNeighboringVerts(vert);
  //        float distance2 = 0;
  //        int farthestVert2 = -1;
  //        for(Integer v : allNeighbors2){
  //          float testDist2 = d(M.G[v],g2);
  //          if(testDist2 > distance2){
  //            distance2 = testDist2;
  //            farthestVert2 = v;
  //          }
  //        }
//          sharedTs2 = sharedTriangles(vert,neighbors[0]);
        } else if(sharedTs2[1]==-1){
          for(int j = 0; j<M.nv; j++){
            if(M.G[j].x == M.G[neighbors[1]].x && M.G[j].y == M.G[neighbors[1]].y && M.G[j].z == M.G[neighbors[1]].z && j!=neighbors[1]){
              try{
                println(neighbors[1]);
                println(j);
              sharedTs2=sharedTriangles(vert,neighbors[1],j);
              } catch (Exception e){
                println(e.toString());
              }
              break;
            }
          }
        }
        
        ArrayList<Integer> halfClose = new ArrayList<Integer>();
        ArrayList<Integer> halfClose2 = new ArrayList<Integer>();
        pt origin = new pt(-10000,-10000,-10000);
        float distance = d(M.triCenter(sharedTs[0]),origin);
        float distance2 = d(M.triCenter(sharedTs[1]),origin);
        int corn;
        int corn2;
        
        corn = M.c(sharedTs[0]);

        while(M.v(corn)!=vert){
          corn=M.n(corn);
        }


        corn2 = M.c(sharedTs[1]);

        while(M.v(corn2)!=vert){
          corn2=M.n(corn2);
        }
        
        
        
        
  //      for(int j = 0; j<closeTriangles.size()/2; j++){
  //        halfClose.add(M.t(corn));
  //        if(closeTriangles.contains(M.t(M.o(corn))) && !halfClose.contains(M.t(M.o(corn)))){
  //          corn = M.n(M.o(corn));
  //          println("ran");
  //        } else {
  //          corn = M.o(M.n(corn));
  //        }
  //      }
//        println("neighbors[" +neighbors[0] + "," + neighbors[1] + "]");
        println("sharedTs[" +sharedTs[0] + "," + sharedTs[1] + "]");
        println("sharedTs2[" +sharedTs2[0] + "," + sharedTs2[1] + "]") ;
        int safetyCount = 0;
        while(M.t(corn)!= sharedTs2[0] && M.t(corn)!=sharedTs2[1] && safetyCount<100){
          safetyCount++;
          halfClose.add(M.t(corn));
          
          println("Vert/Corn " + vert + " " + M.t(corn));
          corn = M.s(corn);
//          if(closeTriangles.contains(M.t(M.o(corn))) && !halfClose.contains(M.t(M.o(corn)))){
//            corn = M.n(M.o(corn));
//  //          println("ran");
//          } else {
//            corn = M.o(M.n(corn));
//          }
        }
        halfClose.add(M.t(corn));
        
        safetyCount = 0;
        while(M.t(corn2)!= sharedTs2[0] && M.t(corn2)!=sharedTs2[1] && safetyCount<100){
          safetyCount++;
          halfClose2.add(M.t(corn2));
          
          println("Vert/Corn " + vert + " " + M.t(corn2));
          corn2 = M.s(corn2);
        }
//        println("Vert/Corn " + vert + " " + M.t(corn));
        halfClose2.add(M.t(corn2));
        
        if(halfClose2.size()<halfClose.size() && sharedTs[1]!=-1){
          halfClose = halfClose2;
        }
        
        pt p = new pt(M.G[vert].x,M.G[vert].y,M.G[vert].z);
        M.G[M.nv] = p;
//        println("vert/new " + vert + "/" + M.nv);
        for (Integer close1 : halfClose){
//          println("c " + close1);
        }
        for(int j = 0; j<M.nt*3; j++){
          if(halfClose.contains(j/3) && M.V[j] == vert){
//            println("j/3 " + j/3);
            M.V[j] = M.nv;
          }
        }
        added.add(M.nv);
        M.nv++;
      }
//      else {
//        println("Skipped " + vert);
//      }
    }
    M.computeVertexNormals();
//    M.updateON();
//    findNonManifoldVerts(added);

    

  }
//  println("THE SIZE IS: "+ verts.size());
//  println(anim + "--" + added.size());
  animateCrack(anim,added);
}

ArrayList<Integer> vertsToMove = new ArrayList<Integer>();
void animateCrack(int anim,ArrayList<Integer> verts){
  Collections.sort(verts,new VertDistComp());
//  println(anim);
  int prevVert = 0;
  int nextVert = 0;
  vec na = new vec(0,0,0);
  vec nb = new vec(0,0,0);
  for(int i = 0; i<verts.size() && anim==1; i++){
    int secondVert = -1;
    for(int j=0; j<verts.size(); j++){
      if(pointEquals(M.G[verts.get(i)],M.G[verts.get(j)]) && verts.get(j).intValue()!=verts.get(i).intValue()){
//        println("i " + verts.get(i).intValue());
//        println("j " + verts.get(j).intValue());
        secondVert = verts.get(j);
        break;
      }
    }
    int vert = verts.get(i);
//    println(vert);
//    println(secondVert);
    if(secondVert==-1) {secondVert = 0; /*println("SV = -1");*/}
    else {
      int [] neighbors = findNeighboringVertsComb(vert, secondVert,verts);
      int [] neighbors2 = null;
  //    if(secondVert != -1){
  //      neighbors2 = findNeighboringVerts(secondVert,verts);
  //    }
//      println(neighbors[0]);
//          println(neighbors[1]);
  
      if(neighbors[1]!=-1 && neighbors[0]!=-1/*i!= 0 && i!=verts.size()-1*/){
  //      na = N(V(M.G[verts.get(i)],M.G[neighbors[0]]),N(M.G[verts.get(i)],M.G[neighbors[0]],M.G[neighbors[1]]));
  //      nb = N(V(M.G[verts.get(i)],M.G[neighbors[1]]),N(M.G[verts.get(i)],M.G[neighbors[0]],M.G[neighbors[1]]));
//        pt mp = P(M.G[neighbors[0]],M.G[neighbors[1]]);
//        na = V(mp,M.G[vert]);
//        println(na.norm());
  //      println(na.toString());
  //      println(nb.toString());
//        na.add(nb);
//        na.normalize();
//        if(M.G[neighbors[0]].x-M.G[neighbors[1]].x>M.G[neighbors[0]].y-M.G[neighbors[1]].y){
//          na = vecRotate90(neighbors[0],neighbors[1],M.Nv[neighbors[1]]);
//        } else {
          na = vecRotate90(neighbors[1],neighbors[0],M.Nv[neighbors[0]]);
//        }
        
        na.normalize();
        na.div(spreadFactor/spreadDivisor*divisions);
//        printvec(M.Nv[neighbors[0]]);
//        printvec(na);
//        printpt(M.G[vert]);
//        printpt(M.G[neighbors[0]]);
//        printpt(M.G[neighbors[1]]);
  //      if(neighbors2 != null){
  //        printpt(M.G[neighbors2[0]]);
  //        printpt(M.G[neighbors2[1]]);
  //      }
  //      printpt(M.G[neighbors[2]]);
  //      printpt(M.G[neighbors[3]]);
        if(pointEquals(M.G[neighbors[0]],M.G[neighbors[1]])){
          na = new vec(0,0,0);
        }
//        na = na.mul(-1);
        if(na.norm() == 0){
  //        try{
  //          na = moveVerts.get(moveVerts.size()-1);
  //        } catch(Exception e) {
  //          if(i%2==0){
  //            na = new vec(-1,0,0);
  //          } else {
  //            na = new vec(1,0,0);
  //          }
  //        }
        }
  //              println(na.toString());
        vertsToMove.add(vert);
//        println("Added " + vert);
//        println("Another size: " + vertsToMove.size());
        moveVerts.add(na);
        
      }
    }
  }
  if(anim==1){
    for(int i = 1; i<moveVerts.size(); i+=2){
      moveVerts.get(i).mul(-1);
    }
    
  }
//  println("Size " + moveVerts.size());
//  println("Another size: " + vertsToMove.size());
  for(int i = anim/spreadDivisor; i<anim/spreadDivisor +1 && i<moveVerts.size()-1; i+=2){
      na = moveVerts.get(i);
//      println("ii " +  i);
      nb = moveVerts.get(i+1);

//    }
    M.G[vertsToMove.get(i)].add(na);
    M.G[vertsToMove.get(i+1)].add(nb);
  }
//  for(int i = 0; i<anim && i<moveVerts.size(); i++){
////    if(i!= 0 && i!=anim-1){
//        na = moveVerts.get(i);
//        na.mul(-1);
//
////    }
//    M.G[vertsToMove.get(i)].add(na);
//  }
}

boolean pointEquals(pt a, pt b){
  return a.x == b.x && a.y == b.y && a.z == b.z;
}

class VertDistComp implements Comparator<Integer>{
  int compare(Integer a,Integer b){
    return ((Float)d(M.G[a],new pt(-10000,-10000,-10000))).compareTo(d(M.G[b],new pt(-10000,-10000,-10000)));
  }
}


